The present invention relates generally to the field of displaying three dimensional (3D) information, and more specifically to a modified Back To Front (BTF) algorithm for the CRT display in a 3D format of sectional data from, for example, a Computed Tomography (CT) scanner.
Medical imaging systems such as CT and magnetic resonance imaging devices, use computer analysis techniques to analyze three dimensional image data of an object such as a human organ. Depending on the orientation of the object and the desired viewpoint of an observer, the three dimensional image data are converted to a two dimensional Cathode Ray Tube (CRT) image of the object. The standard BTF algorithm can generate two dimensional images of three dimensional objects without the need for time consuming surface contour or boundary detection computations. An object composed of individual "voxel" elements can be displayed without extracting information about the object's surface. A voxel is a parallelepiped data element used to generate a two dimensional pixel, or CRT picture element, of an object. Key to the BTF algorithm is the order in which the voxels are scanned to produce a final projected image. Later-scanned (front) voxels are used to generate pixels that overwrite and hence hide pixels from earlier-scanned (back) voxels. Furthermore, since the BTF algorithm does not require the checking of a projected voxel's depth, as do algorithms requiring surface information, the display memory is updated by a relatively quick write operation rather than a read, check for depth, and write operation of the other methods. Pixels on the CRT have a brightness proportional to the proximity of the voxel to the front or back of the object being viewed.
A standard BTF algorithm requires input data along about 40 parallel planes through an object. Each plane typically consists of 512.times.512 pixels. To conserve computer memory, each slice can be compressed to 256.times.256 pixels when read from the data storage disk. Next the data are "cuberilled" (converted to cubic voxel elements) by interpolating between the planes to calculate 256 uniformly spaced intermediate planes, thereby creating a volume containing 256.times.256.times.256=16,777,216 voxels. Each voxel represents a data element with a value p located in a three dimensional "object space" by the Cartesian coordinate triplet, Xv, Yv, and Zv. The data value p represents a property of the object, such as density, at that space location.
Where the specimen being scanned is a patient lying face up, the origin of the object coordinate system is usually at the patient's head. The Z axis runs through the head to the feet, the X axis runs through the ears, and the Y axis runs from the forehead to the back of the head. Voxels in each plane have a constant Z value.
Each voxel is then converted to a binary 0 or 1 either by comparison to a look up table or by comparison to a threshold level. As described by Frieder et al. in "Back-to-Front Display of Voxel Based Objects," IEEE Computer Graphics and Applications, Jan. 1985, pp. 55-60, implementation of the standard BTF algorithm involves reading voxels in a three dimensional array starting at the farthest corner from the observer's viewpoint and proceeding in order of increasing X, Y, and Z values. The algorithm then requires transforming the converted voxels for CRT display. In practice, each plane is read from disk storage to memory in order of plane (i.e., Z value), and is scanned and printed in order of increasing X and Y within each plane. "Front" planes overwrite "back" planes and hide the earlier written voxels. A front plane is the plane closest to the observer's viewpoint and either has the lowest or highest value of Z depending on the observer's location.
An observer's viewpoint or viewing position is referenced to the object coordinate system by its position, Xe, Ye, and Ze, in that coordinate system and by the direction of view, defined as the three angles a vector in this direction would make with the object coordinate system axes.
An image coordinate system for a CRT is defined by an X axis parallel to the bottom of the CRT, a Y axis parallel to the left edge of the CRT, and a Z axis projecting into the front face of the CRT. This coordinate system defines the "image space."
A transformation matrix maps the voxel data in object space at Xv, Yv, Zv into pixel data in image space at Xi, Yi, Zi. The Xi and Yi coordinates locate the pixel on the screen, and the brightness is set by the value of Zi. The viewing position and attitude transformations can be combined in a single 4.times.4 matrix or can be computed separately as a 3.times.3 matrix and a translation (addition) operation. A drawback of the standard BTF methods is that 3D image reconstruction typically requires up to 16 million matrix transformations involving a very large number of multiplications. The standard BTF transformations using a 3.times.3 matrix, and ignoring translation components, consist of: ##EQU1## EQU Xi=a*Xv+d*Yv+g*Zv EQU Yi=b*Xv+e*Yv+h*Zv (2) EQU Zi=C*Xv+f*Yv+i*Zv
Because voxels are transformed one plane at a time, the Zv values are constant for the entire plane. The transformation calculations may therefore be simplified to: EQU Xi=a*Xv+d*Yv+K1; where K1=g*Zv EQU Yi=b*Xv+e*Yv+K2; where K2=h*Zv (3) EQU Zi=c*Xv+F*Yv+K3; where K3=i*Zv
The constants K1, K2, and K3 are calculated only once per plane, and the translation values can easily be included with them. Within each plane, the voxels are transformed one line at a time such that the Yv value along each line is constant. The transformation equations may thus be further simplified to: EQU Xi=a*Xv+K4; where K4=d*Xv+K1 EQU Yi=b*Xv+K5; where K5=e*Yv+K2 (4) EQU Zi=c*Xv+K6; where K6=f*Yv+K3
The constants K4, K5, and K6 are calculated only once per line. To aid computation further, adjacent voxels on a line are transformed to an incremental calculation, simplifying the transformation equations to: EQU [Xi].sub.u+1 =[Xi].sub.u +a EQU [Yi].sub.u+1 =[Yi].sub.u +b (5) EQU [Zi].sub.u+1 =[Zi].sub.u +c
Even with the simplifications introduced by equations (3)-(5), the standard BTF algorithm just described is slow, typically requiring several millions of computations per image, and the resultant image may have aliasing artifacts if the observer's viewpoint is too close to the object, which results in adjacent voxels mapping to non-adjacent pixels, hence holes appear in the image.
It is therefore an object of the present invention to reduce the number of transformations needed to project an image using a BTF algorithm.
It is another object of the present invention to reduce aliasing artifacts by resampling the voxel data in one dimension as a function of the pixel resolution of the screen.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the appended claims.